package subString;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

public class subarraySum {
    // 前缀和+枚举
    // 一开始以为能排序，但题目要求为连续元素构成的子数组，所以不能排序，因此就没有单调性可言，就不能进行优化了
    public static int subarraySum1(int[] nums, int k) {
        // 不能排序
        // Arrays.sort(nums);
        // 找到最后一个<=k的index，缩小遍历的范围
        int[] prefixSum = new int[nums.length + 1];

        int index = 0;
        for (int i = 1; i <= nums.length; i++) {
            if (i > 0) {
                // 搞清楚下标的含义
                prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
            }
            // if (k <= nums[i-1]) {
            // prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
            // index = i;
            // break;
            // }

        }

        // 子数组元素要求连续
        int count = 0;
        for (int i = nums.length; i >= 0; i--) {
            // 不一定从大到小
            // if (prefixSum[i] < k) {
            // break;
            // }
            for (int j = 0; j < i; j++) {
                // 不一定从大到小
                if (prefixSum[i] - prefixSum[j] == k) {
                    count++;
                }
            }
        }
        return count;
    }

    // 上述代码可以优化，在下面的循环中，可以用hashmap
    // 为何不能用hashset，因为可能出现1 -1 0 ——0的情况，前缀和相同，会覆盖，导致漏解，因此用map，统计所有相同的前缀和结果
    public static int subarraySum2(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        // 前缀和结果直接放在map中，无需放在数组中
        // 初始化0
        map.put(0, 1);
        int sum = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 先判断再存放
            if (map.containsKey(sum - k)) {

                Integer value = map.get(sum - k);
                count += value;
            }
            if (map.containsKey(sum)) {
                Integer value = map.get(sum);
                map.put(sum, value + 1);

            } else {
                map.put(sum, 1);
            }

        }

        return count;
    }

    public static void main(String[] args) {
        // int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        // int[] nums = new int[] { 1, 1,1 };
        // int[] nums = new int[] { -1, -1,1 };
        int[] nums = new int[] { 1, -1, 0 };
        int subarraySum = subarraySum2(nums, 0);
        System.out.println(subarraySum);
    }
}
